import java.util.ArrayDeque;

/**
 * @author dragon
 * @since 2019/12/23
 */
public class Test8 {

    public static void main(String[] args) {
        Test8 test8 = new Test8();
        String s = test8.addBinary2("100", "110010");
        System.out.println(s);
    }

    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int carryBit = 0;
        int sum;
        for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--) {
            sum = carryBit;
            sum += i >= 0 ? a.charAt(i) - '0' : 0;
            sum += j >= 0 ? b.charAt(j) - '0' : 0;
            sb.append(sum % 2);
            carryBit = sum / 2;
        }
        if(carryBit == 1) {
            sb.append("1");
        }

        return sb.reverse().toString();
    }

    public String addBinary2(String a, String b) {
        StringBuilder sb = new StringBuilder();
        ArrayDeque<Character> stack = new ArrayDeque();
        int loopCount = a.length() > b.length() ? a.length() : b.length();
        for (int i = 1; i <= loopCount; i++) {
            if (i <= a.length()) {
                stack.push(a.charAt(a.length() - i));
            }
            if (i <= b.length()) {
                stack.push(b.charAt(b.length() - i));
            }
            int top = 0;
            if (!stack.isEmpty()) {
                top = stack.pop();
            }
            int secondTop = 0;
            if (!stack.isEmpty()) {
                secondTop = stack.pop();
            }
            int thirdTop = 0;
            if (!stack.isEmpty() && stack.peek().equals('1')) {
                thirdTop = stack.pop();
            }
            int sum = top + thirdTop + secondTop;
            // '1' + '1'
            if (sum == 98) {
                sb.append("0");
                stack.push('1');
                // '0' + '1'
            } else if (sum == 97) {
                sb.append("1");
                // '1' + '1' + '1'
            } else if (sum == 147) {
                sb.append("1");
                stack.push('1');
                // '0' + '0'
            } else if (sum == 96) {
                sb.append("0");
                // '0' + '1' + '1'
            } else if (sum == 146) {
                sb.append("0");
                stack.push('1');
                // '0' + '0' + '1'
            } else if (sum == 145) {
                sb.append("1");
                // '0'
            } else if (sum == 48) {
                sb.append("0");
            } else if (sum == 49) {
                sb.append("1");
            }
        }
        if (!stack.isEmpty()) {
            sb.append(stack.pop() + "");
        }

        return sb.reverse().toString();
    }
}
